package strs

/*
通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
*/

func WildcardMatch(s string, p string) bool {
	if p == "*" {
		return true
	}
	if len(s) == 0 {
		for i := 0; i < len(p); i++ {
			if p[i] != '*' {
				return false
			}
		}
		return true
	}
	if len(p) == 0 {
		return false
	}
	//先反向匹配到*
	ls := len(s) - 1
	lp := len(p) - 1
	for ls >= 0 && lp >= 0 {
		if p[lp] == '*' {
			break
		}
		if p[lp] == '?' || p[lp] == s[ls] {
			ls--
			lp--
		} else {
			return false
		}
	}
	//判断是否收尾
	if ls == -1 {
		for i := 0; i <= lp; i++ {
			if p[i] != '*' {
				return false
			}
		}
		return true
	}
	if lp == -1 {
		return false
	}
	//p[lp] == '*'
	//从前面开始匹配
	i := 0
	j := 0
	i1 := -1 //回退匹配点
	j1 := -1
	for i <= ls && j < lp {
		if p[j] == '*' {
			j++
			i1, j1 = i, j
		} else if p[j] == '?' || p[j] == s[i] {
			i++
			j++
		} else if i1 != -1 && i1 < ls { //遇到了*，将i1匹配给*
			//回退到下一个位置开始比对,如果没有回退的位置则返回失败
			i = i1 + 1
			i1, j = i, j1
		} else {
			return false
		}
	}
	//收尾
	for j < lp {
		if p[j] != '*' {
			return false
		}
		j++
	}
	return true
}
